package Runde5;


public abstract class Tree<A extends Comparable<? super A>> {
	
	protected Node root;
	
	/**
	 * @precondition root != null
	 * @postcondition Creates a new tree with the root labeled by the given object.
	 */
	public Tree(A root){
		this.root = new Node(root);
	}
	
	/**
	 * @precondition label != null
	 * @postcondition Searches tree for node with given label, if found TreeIter with found node as "root" will be returned, else null
	 */
	public TreeIter<A> contains(A label) {
		Iter<Boolean> iter = search(label);
		if (iter == null) {
			return null;
		}
		
		Node node = root;
		while (iter.hasNext()) {
			if (iter.next()) {
				node = node.getRightChild();
			} else {
				node = node.getLeftChild();
			}
		}
		return new Iterator(node);
	}
	
	/**
	 * @precondition label != null
	 * @postcondition Returns Boolean-Iterator which describes the path from the root of the tree to a node with the given label (true=right, false=left),
	 * 					returns null if no matching node was found
	 */
	public Iter<Boolean> search (A label) {
		List<Boolean> temp1 = depthFirstSearch(label, root);
		if (temp1 == null) {
			return null;
		}
		List<Boolean> temp2 = new List<Boolean>();
		Iter<Boolean> t1iter = temp1.iterator();
		while (t1iter.hasNext()) {
			t1iter.next();
		}
		t1iter.next();
		while (t1iter.hasPrevious()) {
			temp2.add(t1iter.previous());
		}
		
		return temp2.iterator();
	}
	
	/**
	 * @precondition wantedLabel != null, currentNode SHOULD be the tree's root in order to search the whole tree
	 * @postcondition Supportive method for search() - searches for a node labeled with "wantedLabel" recursivly, returns Boolean-List if found, and null if not
	 */
	private List<Boolean> depthFirstSearch(A wantedLabel, Node currentNode) {
		if (currentNode == null) {
			return null;
		}		
		A curLabel = currentNode.getLabel();
		
		if (curLabel.compareTo(wantedLabel) == 0) {
			return new List<Boolean>();
		}
		List<Boolean> resultleft = depthFirstSearch(wantedLabel, currentNode.getLeftChild());
		List<Boolean> resultright = depthFirstSearch(wantedLabel, currentNode.getRightChild());
		if (!(resultleft == null)) {
			resultleft.add(false);
			return resultleft;
		}
		if (!(resultright == null)) {
			resultright.add(true);
			return resultright;
		}
		return null;	
	}
	
	/**
	 * @postcondition Returns new iterator over the whole CURRENT tree
	 * 					If tree is changed the iterator won't be updated, you have to instantiate a new one.
	 */
	public TreeIter<A> iterator() {
		return new Iterator(root);
	}
	
	/**
	 * @precondition label != null
	 * @postcondition Adds a new node with given label to the tree.
	 */
	public abstract void add(A label);
	
	/**
	 * @precondition label != null
	 * @postcondition determines in which way nodes are added to the iterator's list, ordering depends on the instanced sub-type of tree 
	 */
	protected abstract void addNodesToList(Node node, List<A> list);

	
	//Node-Class
	protected class Node {
		
		private A label;
		private Node leftChild;
		private Node rightChild;
		
		/**
		 *  @precondition label != null
		 *  @postcondition creates a new node with given label
		 */
		public Node(A label) {
			this.label = label;
		}
		
		/**
		 * @postcondition Sets the node's right child
		 * @param rightChild - Node to set as right child
		 */
		public void setRightChild(Node rightChild) {
			this.rightChild = rightChild;
		}

		/**
		 * @postcondition Returns the node's right child
		 */
		public Node getRightChild() {
			return rightChild;
		}
		
		/**
		 * @postcondition Sets the node's left child
		 * @param rightChild - Node to set as left child
		 */
		public void setLeftChild(Node leftChild) {
			this.leftChild = leftChild;
		}

		/**
		 * @postcondition Returns the node's left child
		 */
		public Node getLeftChild() {
			return leftChild;
		}
		
		/**
		 * @postcondition Returns the node's label
		 */
		public A getLabel() {
			return label;
		}
	}
	
	//Iterator-Class
	protected class Iterator implements TreeIter<A> {

		A current;
		boolean somethingHappened;
		List<A> nodeList;
		Iter<A> iter;
		
		/**
		 * @postcondition Creates a new Iterator (TreeIter), which iterates over the CURRENT (sub-)tree with given node as root. Which type of traversal is used
		 * 					depends on the tree's implementation of addNodesToList, if null is given iterator over empty list is returned
		 * 					If (sub-)tree is changed the iterator won't be updated, you have to instantiate a new one.
		 */
		public Iterator(Node node) {
			nodeList = new List<A>();
			if (node != null) {
				addNodesToList(node,nodeList);
			}
			iter = nodeList.iterator();
			somethingHappened = false;
		}
		
		/**
		 * @postcondition Returns a new iterator which only iterates over the CURRENT "current" node (= the node matching the "current" label) and it's subtree.
		 * 					If there are no calls of next() or previous() yet: returned iterator iterates over "next()" and it's subtree.
		 * 					If current label is null, an iterator over a empty list is returned (see public Iterator(Node node))
		 * 					If (sub-)tree is changed the iterator won't be updated, you have to instantiate a new one.
		 */
		public TreeIter<A> down() {
			A label;
			if (!somethingHappened) {
				label = next();
				previous();
			} else {
				label = current;
			}
			TreeIter<A> returnVal = contains(label);
			if (label == null || returnVal == null) {
				return new Iterator(null);
			}
			return returnVal;

		}

		/**
		 * @postcondition Returns true if next() != null.
		 */
		public boolean hasNext() {
			return iter.hasNext();
		}

		/**
		 * @postcondition Returns true if previous() != null.
		 */
		public boolean hasPrevious() {
			return iter.hasPrevious();
		}

		
		/**
		 * @postcondition Places iterator on next element in list and returns it.
		 */
		public A next() {
			somethingHappened = true;
			current = iter.next();
			return current;
		}

		/**
		 * @postcondition Places iterator on previous element in list and returns it.
		 */
		public A previous() {
			somethingHappened = true;
			current = iter.previous();
			return current;
		}
		
		
	}

}
